package com.leet.code.simple_array;

import java.util.Arrays;

/**
 * @description:
 * @author: WYG
 * @time: 2020/12/11 9:26
 */

public class HeightChecker {
    public int heightChecker(int[] heights) {
        int[] height = Arrays.copyOf(heights, heights.length);
        int res = 0;
        Arrays.sort(heights);
        for (int k = 0; k < heights.length; k++) {
            if (heights[k] != height[k]) {
                res++;
            }
        }
        return res;
    }
    public int FasterHeightChecker(int[] heights) {
        int[] arr = new int[101];
        for (int height : heights) {
            arr[height]++;
        }
        int count = 0;
        for (int i = 1, j = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                if (heights[j++] != i) count++;
            }
        }
        return count;
    }
}
